Послідовний контейнер
В програмуванні, послідовний контейнер це ціла група шаблонів класів стандартної бібліотеки мови C++, які реалізують логіку контейнера, що виконує функцію зберігання елементів даних. Будучи шаблонами, вони можуть використовуватися для зберігання довільних елементів, як для цілих чисел так і для користувацьких класів. Спільною властивістю всіх послідовних контейнерів в тому, що доступ до елементів відбувається послідовно. Як і всі інші стандартні компоненти бібліотеки, вони знаходяться в просторі імен std.
В останньому стандарті С++ визначені наступні контейнери: array, vector, list, forward_list, deque. Кожен з цих контейнерів реалізує різні алгоритми зберігання даних, це означає, що вони мають різну швидкодію при виконанні різних операцій:[1]
arrayреалізує масив незмінного розміру, що створюється під час компіляції.vectorреалізує масив із швидким довільним доступом і можливістю автоматичної зміни розміру при додаванні елементів.dequeреалізує двобічну чергу з порівняно швидким довільним доступом до елементів.listреалізує двобічно зв'язаний список.forward_listреалізує однобічно зв'язаний список.
Оскільки кожен з контейнерів потребує можливості копіювати свої елементи для правильного функціонування, тип даних елементу має виконувати вимоги CopyConstructible і Assignable (мати конструктор копій і оператор присвоювання).[2] У даного контейнера, всі елементи мають бути одного типу. Наприклад, не можливо одночасно зберігати дані типу char і int в одному контейнері.
Спочатку, тільки були визначені лише класи vector, list, deque. До стандартизації мови C++ в 1998, вони були частиною Стандартної бібліотеки шаблонів, що була опублікована компанією SGI.
Контейнер array вперше з’явився у декількох книжках під різними назвами. Згодом він був вбудований в в набір бібліотек Boost C++ і був запропонований в стандартну бібліотеку C++.
Мотивацією додавання контейнера array було те, що він вирішував дві проблеми масивів Cі-стилю: нестачу STL-подібного інтерфейсу і неможливість копіювати його як будь-який інший об'єкт.
Він вперше з’явився в C++ TR1 і згодом став частиною стандарту C++11.
Контейнер forward_list було додано до C++11 як більш просторово-ефективна альтернатива стандартному контейнеру list для випадків, коли зворотній прохід ітератора не потрібний.
array, vector і deque - всі ці контейнери підтримують довільний доступ до елементів. list підтримує двонаправлену ітерацію, тоді як forward_list підтримує ітерування лише в одному напрямку.
array не має функції додавання чи видалення елементів. vector дозволяє швидко додавати чи видаляти елементи в кінці вектора. Будь-яке додавання чи видалення елементів не в кінці вектора потребує виконувати операцію копіювання елементів від позиції додавання елементів до кінця вектору. Ітератори над елементами, з якими відбулися такі дії стають недійсними. Насправді, будь-яке додавання має шанс порушити і зробити недійсними всі ітератори. Крім того, якщо виділене сховище пам'яті у vector замале, для додавання нових елементів, буде виділено новий масив в пам'яті, всі елементи будуть скопійовані і перенесені у новий масив, а старий масив буде вивільнено. Контейнери deque, list і forward_list підтримують операції швидкого додавання або видалення елементів, в будь-яке місце контейнеру. list і forward_list зберігають валідність ітераторів при таких операціях, а deque робить їх всі недійсними.
Елементи контейнера vector зберігаються послідовно.[3] Як і всі реалізації динамічних масивів, вектори дозволяють ефективно використовувати пам'ять і мають добру локалізацію посилань[en] і оптимальне використання кешу. На відміну від інших STL контейнерів, таких як двобічні черги (deque) і списки (list), вектори дозволяють вказувати початковий розмір контейнера.
Вектори дозволяють здійснювати довільний доступ; таким чином, що до елементів вектору можна доступатися таким самим чином як і до елементів масивів (по індексу в масиві).
- ↑ Josuttis, Nicolai (1999). C++ Standard Library - A Tutorial and Reference. Addison-Wesley.
- ↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.1 Container requirements [lib.container.requirements] para. 4
- ↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §23.2.4 Class template vector [lib.vector] para. 1